package com.sicheng.lc.周赛.分类.秒杀子数组类题目基本原理_前缀和_滑动窗体_数论;

import java.util.Arrays;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/7/11 11:12
 */
public class 和可被K整除的子数组 {
    //https://leetcode.cn/problems/subarray-sums-divisible-by-k/
    // 同余定理
    //  a%k=x ,b%k=y
    //  核心是减法的同余需要把负数规约到正数上
    //  (a-b)%k=(x-y+k)%k
    //  (a+b)%k=(x+y)%k
    //  (a*b)%k=(x*y)%k
    static int[] map = new int[(int) 1e4 + 1];

    {
        Arrays.fill(map, 0);
        map[0] = 1;
    }

    //   对于前缀和而言，当前的sum[i]期待之前出现了sum[j]满足
    //   sum[i] % k == sum[j] % k ==> (sum[i]-sum[j])%k==0
    public int subarraysDivByK(int[] nums, int k) {
        int sum = 0;
        int res = 0;
        for (int num : nums) {
            sum = (sum + num) % k;
            sum = (sum + k) % k;
            res += map[sum];
            map[sum]++;
        }
        return res;
    }
}
